package org.blogwu.learn.leetcode.二叉树;

public class BinarySearchTree {


    private int size;

    /**
     * 二叉树根节点
     */
    public TreeNode root;

    /**
     * 元素数量
     *
     * @return
     */
    public int size() {
        return this.size;
    }

    /**
     * 是否为空
     *
     * @return
     */
    public boolean isEmpty() {
        return this.size < 1;
    }

    /**
     * 清空所有元素
     */
    public void clear() {

    }

    /**
     * 添加元素
     */
    public void add(int val) {
        // 初始化根节点
        if (root == null) {
            root = new TreeNode(val);
            size++;
            return;
        }
        // 非第一个节点
        TreeNode node = root;
        TreeNode parent = root;
        int cmp = 0;
        // 一直遍历
        while (node != null) {
            cmp = val - node.val;
            // 保存父节点
            parent = node;
            if (cmp > 0) {
                node = node.right;
            } else if (cmp < 0) {
                node = node.left;
            } else {  // 相等
                node.val = val;
                return;
            }
        }
        // 插入节点
        TreeNode newNode = new TreeNode(val);
        // 保存父节点
        if (cmp > 0) {
            parent.right = newNode;
        } else {
            parent.left = newNode;
        }
        size++;
    }

}
